package leetcode_day._2022._202209._0110;

import java.util.Arrays;

/**
 * 828. 统计子串中的唯一字符
 * 算法：模拟 + 数学(乘法原理)
 * 求出某个字符左边与之相同的第一个字符的距离和右边与之相同的第一个字符的最远距离,
 * 两个距离相乘就是这个字符在字串中的数量(字串中该字符字符唯一)
 * ABC, A 的左边最远距离为 -1, 右边最远距离为 3
 * _ 代表空
 * 左边的字符(_), 右边的字符(B, BC, _), 所以 A 就是 3
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/6 21:50
 */
public class _06 {

    public int uniqueLetterString(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, ans = 0;
        int[] l = new int[n], r = new int[n], idx = new int[26];
        Arrays.fill(idx, -1);
        for (int i = 0; i < n; i++) {
            int u = cs[i] - 'A';
            l[i] = idx[u];
            idx[u] = i;
        }
        Arrays.fill(idx, n);
        for (int i = n - 1; i >= 0; i--) {
            int u = cs[i] - 'A';
            r[i] = idx[u];
            idx[u] = i;
        }
        for (int i = 0; i < n; i++) ans += (i - l[i]) * (r[i] - i);
        return ans;
    }

}
